/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: jzj
 * Date: 2024-03-24
 * Time: 14:13
 */
public class test_1 {
    public static int waysToStep(int n) {
        int MOD = (int) 1e9 + 7;
        //1.建立dp表
        int[] dp = new int[n + 1];
        //2.初始化
        dp[0] = 1;
        if (n == 1) {
            return 1;
        }
        dp[1] = 1;
        if (n == 2) {
            return 2;
        }
        dp[2] = 2;
        //3.填表
        for (int i = 3; i < dp.length; i++) {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        }
        return dp[n];

    }

    public static void main(String[] args) {
        int ret = waysToStep(61);
        System.out.println(ret);
    }

}
